905. Sort Array By Parity

tags: Easy、Sort

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.

解法1: Double Foor Loop

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParity(int* nums, int numsSize, int* returnSize) {
    if (!nums) {
        *returnSize = 0;
        return NULL;
    }

    *returnSize = numsSize;
    int* sort = (int*)calloc(*returnSize, sizeof(int));
    int sortSize = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] % 2 == 0) {
            sort[sortSize] = nums[i];
            sortSize++;
        }
    }
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] % 2 != 0) {
            sort[sortSize] = nums[i];
            sortSize++;
        }
    }

    return sort;
}

解法2:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParity(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* sort = (int*)calloc(*returnSize, sizeof(int));
    int head = 0;
    int tail = numsSize - 1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] % 2 == 0) {
            sort[head++] = nums[i];
        }
        else {
            sort[tail--] = nums[i];
        }
    }
    return sort;
}

922. Sort Array By Parity II

tags: Easy、Sort

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.

解法:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParityII(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* sort = (int*)calloc(*returnSize, sizeof(int));
    int even = 0;
    int odd = 1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] % 2 == 0) {
            sort[even] = nums[i];
            even += 2;
        }
        else {
            sort[odd] = nums[i];
            odd += 2;
        }
    }
    return sort;
}

1122. Relative Sort Array

tags: Easy、Tree

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.
Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

解法1: 直接比較

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void bubbleSort(int* array, int arraySize) {
    for (int i = 0; i < arraySize - 1; i++) {
        for (int j = 0; j < arraySize - 1 - i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    *returnSize = arr1Size;
    int* sort = (int*)calloc(arr1Size, sizeof(int));
    int* uni_sort = (int*)calloc(arr1Size, sizeof(int)); //儲存不同元素的陣列
    int count_same = 0;
    int count_uni = 0;

    for (int i = 0; i < arr2Size; i++) {
        for (int j = 0; j < arr1Size; j++) {
            if (arr2[i] == arr1[j]) {
                sort[count_same++] = arr1[j];
            }
        }
    }

    for (int i = 0; i < arr1Size; i++) {
        bool found = false;
        for (int j = 0; j < arr2Size; j++) {
            if (arr1[i] == arr2[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            uni_sort[count_uni++] = arr1[i];
        }
    }

    bubbleSort(uni_sort, count_uni);
    for (int i = 0; i < count_uni; i++) {
        sort[count_same++] = uni_sort[i];
    }

    return sort;
}

解法2: 建立檢查表

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    *returnSize = arr1Size;
    int check[1001] = {0};
    int* sort = (int*)calloc(arr1Size, sizeof(int));
    if (!sort) {
        *returnSize = 0;
        return NULL;
    }
    int index = 0;

    //建立檢查表
    for (int i = 0; i < arr1Size; i++) {
        check[arr1[i]]++;
    }

    for (int i = 0; i < arr2Size; i++) {
        while(check[arr2[i]] > 0) {
            sort[index++] = arr2[i];
            check[arr2[i]]--;
        }
    }

    for (int i = 0; i < 1001; i++) {
        while (check[i] > 0) {
            sort[index++] = i;
            check[i]--;
        }
    }
    return sort;
}

2418. Sort the People

tags: Easy、Sort

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.
For each index i, names[i] and heights[i] denote the name and height of the ith person.
Return names sorted in descending order by the people's heights.

解法1:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {
    *returnSize = heightsSize;

    for (int i = 0; i < heightsSize - 1; i++) {
        for (int j = 0; j < heightsSize - 1 - i; j++) {
            if (heights[j] < heights[j+1]) {
                int tempHeight = heights[j];
                heights[j] = heights[j+1];
                heights[j+1] = tempHeight;

                char* tempName = names[j];
                names[j] = names[j+1];
                names[j+1] = tempName;
            }
        }
    }
    return names;
}

解法2: 較快&較好

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int intcmp(const void* a, const void* b) {return *(int*)b - *(int*)a;}
char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {
    *returnSize = heightsSize;
    char** sort = (char**)malloc(heightsSize * sizeof(char*));
    //cause n < 1000, <<10 is enough
    for (int i = 0; i< heightsSize; i++) {
        heights[i] = (heights[i] << 10) + i;
    }
    qsort(heights, heightsSize, sizeof(int), intcmp);

    for (int i = 0; i< heightsSize; i++) {
        sort[i] = names[heights[i]&0x3FF];
    }
    return sort;
}